package exam.bak.ali;

import java.util.*;

public class P2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //1. 录入参数
        String[] params = scanner.nextLine().trim().split("\\s+");
        int n = Integer.parseInt(params[0]); //城市数
        int m = Integer.parseInt(params[1]); //道路数
        //开放因子
        int[] w = Arrays.stream(scanner.nextLine().trim().split("\\s+")).mapToInt(Integer::valueOf).toArray();
        //修整时间
        int[] p = Arrays.stream(scanner.nextLine().trim().split("\\s+")).mapToInt(Integer::valueOf).toArray();
        //连接城市及长度
        int[][] roads = new int[m][3];
        for (int i = 0; i < m; i++) {
            roads[i] = Arrays.stream(scanner.nextLine().trim().split("\\s+")).mapToInt(Integer::valueOf).toArray();
        }
        params = scanner.nextLine().trim().split("\\s+");
        int s = Integer.parseInt(params[0]);
        int t = Integer.parseInt(params[1]);
        //2. 计算
        System.out.println(solve(roads, n, m, w, p, s, t));
    }

    private static int solve(int[][] roads, int n, int m, int[] w, int[] p, int s, int t) {
        //1. 记录道路连接关系, 及城市间到来花费
        Map<Integer, List<Integer>> linkMap = new HashMap<>();
        int[][] cost = new int[n + 1][n + 1];
        for (int[] road : roads) {
            List<Integer> list = linkMap.getOrDefault(road[0], new ArrayList<>());
            list.add(road[1]);
            linkMap.put(road[0], list);
            cost[road[0]][road[1]] = road[2];
            cost[road[1]][road[0]] = road[2];
        }
        //2. 计算
        int[] result = new int[]{Integer.MAX_VALUE};
        dfs(m, linkMap, cost, w, p, s, s, t, 0, result);
        return result[0] == Integer.MAX_VALUE ? -1 : result[0];
    }

    private static void dfs(int times, Map<Integer, List<Integer>> linkMap, int[][] cost, int[] w, int[] p, int begin, int s, int t, int total, int[] result) {
        if (times <= 0 && s != t) {
            return;
        }
        if (s == t) {
            result[0] = Math.min(total, result[0]);
        } else {
            if (linkMap.containsKey(s)) {
                List<Integer> citys = linkMap.get(s);
                for (int city : citys) {
                    int sum = 0;
                    //上一个城市的入城时间
                    if (begin != s) {
                        int w_i = w[city - 1];
                        for (int i = 0; ; i++) {
                            sum = i * w_i;
                            if (sum >= total) {
                                break;
                            }
                        }
                    }
                    sum += p[s - 1];//上一个城市的修整时间
                    sum += cost[s][city]; //当前道路花费
                    dfs(times - 1, linkMap, cost, w, p, begin, city, t, sum, result);
                }
            }
        }
    }
}
